import java.io.*;
import java.util.*;

/**
 * Solver.java - a program for finding solutions to sliding block puzzles.
 * 
 * @author Jim McAllister
 * @author jam(AT)mc-allister(DOT)com
 * 
 * @version 0.1
 *
 */
public class Solver {
	private static final int UP = 1;
	private static final int RIGHT = 2;
	private static final int DOWN = 3;
	private static final int LEFT = 4; 
	
	private Hashtable<Integer, String> table = new Hashtable<Integer, String>(512);
	private Solution s;
	private boolean solved = false;
	private static boolean debug = false;
	private Stack<String> moves = new Stack<String>();
	
	
	/**
	 * Contains configuration of blocks in the puzzle and provides methods for 
	 * manipulating their arrangement.
	 *
	 */
	public class Board{
		private int rows,	// rows of board, 0 based
					cols,	// columns of board, 0 based
					area,	// area of board occupied by blocks
					pieces; // number of blocks on board
		private Block[][] layout;  //r x c array of blocks on board
		private ArrayList<Location> spaces; //array of locations of 1x1 spaces on board
		
		public Board(){
		}
		/*
		 * iterations are a little lengthy, but this will only be initial constructor
		 * future boards will be returned by a factory method TBD (moveBlk???)
		 */
		public Board(int r, int c, ArrayList<Block> blks, ArrayList<Location> locs){
			rows = r;
			cols = c;
			pieces = blks.size();
			layout = new Block[rows][cols];
			area = 0;
			for (int i = 0; i < blks.size(); i++){
				layout[locs.get(i).getRow()][locs.get(i).getCol()] = blks.get(i);
				area += blks.get(i).getHeight() * blks.get(i).getWidth();
			}
			getSpaces(copyLayout(layout));
		}
		
/*		public Board(Board b){
			rows = b.rows;
			cols = b.cols;
			area = b.area;
			pieces = b.pieces;
			layout = b.layout.clone();
			spaces = (ArrayList<Location>)b.spaces.clone();
		}
*/		
		public Board clone(){
			Board b = new Board();
			b.rows = this.rows;
			b.cols = this.cols;
			b.area = this.area;
			b.pieces = this.pieces;
			b.layout = copyLayout(this.layout);
			b.spaces = new ArrayList<Location>();
			for (Iterator<Location> it = this.spaces.iterator(); it.hasNext(); ){
				b.spaces.add(it.next());
			}
			return b;
		}
		
		private Block[][] copyLayout(Block[][] l){
			int x = rows;
			int y = cols;
			Block[][] newLayout = new Block[x][y];
			for (int i = 0; i < x; i++){
				for (int j = 0; j < y; j++){
					if (l[i][j] != null)
						newLayout[i][j] = l[i][j];
				}
			}
			return newLayout;
		}
		
		/**
		 * Determines where vacant 1x1 squares are on the initial board configuration
		 * and sets the spaces field to contain an array of the Location of the vacant 
		 * squares. 
		 * @param blks -  a clone of the layout array that represents the board.
		 */
		void getSpaces(Block[][] blks){
			spaces = new ArrayList<Location>((rows * cols) - area);
			for (int r = 0; r < rows; r++){
				for (int c = 0; c < cols; c++){
					if (blks[r][c] != null && blks[r][c].getWidth() != -1){
						int w = blks[r][c].getWidth();
						int h = blks[r][c].getHeight();
						for (int i = r; i < (r + h); i++){
							for (int j = c; j < (c + w); j++){
								if (blks[i][j] == null)
									blks[i][j] = new Block(0, -1);
							}
						}
					} else
						if (blks[r][c] == null)
							spaces.add(new Location(r, c)); 
				}
			}
		}
		
		/**
		 * Determine if a move is allowable for a given block at a specific location.
		 * @param blk - the block to be moved.
		 * @param from - the location that the block is currently and will be moving from.
		 * @param dir - the direction in which the block is to move.
		 * @return A boolean value; true if move is possible, false otherwise.
		 */
		public boolean moveExists(Location from, int dir){
			int r, c, blkW, blkH, numRows, numCols;
			Block blk;
			boolean canMove = true;
			if (!blockExists(from))
				return false;
			else{
				blk = getBlock(from);
			}
			r = from.getRow();
			c = from.getCol();
			blkW = blk.getWidth();
			blkH = blk.getHeight();
			switch (dir){
			case UP: //move UP
				r--;
				if (r < 0)		//off edge of board
					canMove = false;
				numCols= c + blkW;
				for (int i = c; 
					i < numCols && canMove;
					i++){
					Location tmpLoc = new Location(r, i);
					if (!isSpace(tmpLoc))
						canMove = false;
				}
				break;
			case RIGHT: //move RIGHT
				c += blkW;
				if (c > cols)	//off edge of board
					canMove = false;
				numRows = r + blkH;
				for (int i = r; 
					i < numRows && canMove;
					i++){
					Location tmpLoc = new Location(i, c);
					if (!isSpace(tmpLoc))
						canMove = false;
				}
				break;
			case DOWN: //move DOWN
				r += blkH;
				if (r > rows)	//off edge of board
					canMove = false;
				numCols = c + blkW;
				for (int i = c; 
					i < numCols && canMove;
					i++){
					Location tmpLoc = new Location(r, i);
					if (!isSpace(tmpLoc))
						canMove = false;
				}
				break;
			case LEFT: //move LEFT
				c--;
				if (c < 0)		//off edge of board
					canMove = false;
				numRows = r + blkH;
				for (int i = r; 
					i < numRows && canMove;
					i++){
					Location tmpLoc = new Location(i, c);
					if (!isSpace(tmpLoc))
						canMove = false;
				}
				break;
			}
			return canMove;
		}
		
		/**
		 * Determine if a specified location is a vacant space.
		 * @param loc - the specific location to look at.
		 * @return A boolean value, true if the location is vacant, false otherwise.
		 */
		boolean isSpace(Location loc){
//			return spaces.contains(loc);
			boolean spc = false;
			for (Iterator<Location> it = spaces.iterator(); it.hasNext(); ){
				if (it.next().equals(loc)){
					spc = true;
					break;
				}
			}
			return spc;
		}
		
		public int getRows(){
			return rows;
		}
		
		public int getCols(){
			return cols;
		}
		
		public Board move(Location loc, int dir){
			debugPrint("    Moving " + strDir(dir) + " from " + loc.toString());
			int height,
				width,
				rowFrom,
				rowTo,
				colFrom,
				colTo;
			Board afterMove = this.clone();
			width = getBlock(loc).getWidth();
			height = getBlock(loc).getHeight();
			rowFrom = loc.getRow();
			colFrom = loc.getCol();
			rowTo = 0;
			colTo = 0;
			switch(dir){
			case UP:
				rowTo = rowFrom - 1;
				colTo = colFrom;
				afterMove.layout[rowTo][colTo] = layout[rowFrom][colFrom];
				afterMove.layout[rowFrom][colFrom] = null;
				for (int i = colFrom; i < colFrom + width; i++){
					Location remLoc = new Location(rowTo, i);
					Location addLoc = new Location(rowTo + height, i);
					for (Iterator<Location> it = afterMove.spaces.iterator(); it.hasNext(); ){
						if (remLoc.equals(it.next()))
							it.remove();
					}
					afterMove.spaces.add(addLoc);
				}
				break;
			case RIGHT:
				rowTo = rowFrom;
				colTo = colFrom + 1;
				afterMove.layout[rowTo][colTo] = layout[rowFrom][colFrom];
				afterMove.layout[rowFrom][colFrom] = null;
				for (int i = rowFrom; i < rowFrom + height; i++){
					Location remLoc = new Location(i, colFrom + width);
					Location addLoc = new Location(i, colFrom);
					for (Iterator<Location> it = afterMove.spaces.iterator(); it.hasNext(); ){
						if (remLoc.equals(it.next()))
							it.remove();
					}
					afterMove.spaces.add(addLoc);
				}
				break;
			case DOWN:
				rowTo = rowFrom + 1;
				colTo = colFrom;
				afterMove.layout[rowTo][colTo] = layout[rowFrom][colFrom];
				afterMove.layout[rowFrom][colFrom] = null;
				for (int i = colFrom; i < colFrom + width; i++){
					Location remLoc = new Location(rowFrom + height, i);
					Location addLoc = new Location(rowFrom, i);
					for (Iterator<Location> it = afterMove.spaces.iterator(); it.hasNext(); ){
						if (remLoc.equals(it.next()))
							it.remove();
					}
					afterMove.spaces.add(addLoc);
				}
				break;
			case LEFT:
				rowTo = rowFrom;
				colTo = colFrom - 1;
				afterMove.layout[rowTo][colTo] = layout[rowFrom][colFrom];
				afterMove.layout[rowFrom][colFrom] = null;
				for (int i = rowFrom; i < rowFrom + height; i++){
					Location remLoc = new Location(i, colTo);
					Location addLoc = new Location(i, colTo + width);
					for (Iterator<Location> it = afterMove.spaces.iterator(); it.hasNext(); ){
						if (remLoc.equals(it.next()))
							it.remove();
					}
					afterMove.spaces.add(addLoc);
				}
				break;
			}
			debugPrint("    Moved from (" + rowFrom + ", " + colFrom + ") to (" +
					rowTo + ", " + colTo + ")");
			return afterMove;			
		}

		public String toString() {
			int k = 0;
			int[] tmp = new int[4 * pieces];
			for (int i = 0; i < rows; i++) {
				for (int j = 0; j < cols; j++){
					if (layout[i][j] != null){
						tmp[k++] = layout[i][j].getHeight();
						tmp[k++] = layout[i][j].getWidth();
						tmp[k++] = i;
						tmp[k++] = j;
					}
				}
			}
			return Arrays.toString(tmp);
		}
		/**
		 * 
		 * @param loc
		 * @return
		 */
		private boolean blockExists(Location loc){
			return (layout[loc.getRow()][loc.getCol()] != null);
		}
		
		private Block getBlock(Location loc){
			return layout[loc.getRow()][loc.getCol()];
		}
		
	}
	
	public boolean tryMoving(Board b){
		chkSolution(b);
		if (solved)
			return true;
		String str = b.toString();
		int key = str.hashCode();
		String val = table.get(key);
		if (val == null){
			table.put(key, str);
			debugPrint(str + "added to table.");
		}
		else {
			b = null;
			return false;
		}
		for (int i = 0; i < b.getRows(); i++){
			for (int j = 0; j < b.getCols(); j++){
				for (int k = 1; k <= 4; k++){
					Location l = new Location(i, j);
					if (b.moveExists(l, k)){
						if (tryMoving(b.move(l, k))){
							storeMove(l, k);
							return true;
						}
					}
				}
			}
		}
		return false;
	}
	
	private void storeMove(Location l, int dir){
		String s;
		int rowFrom = l.getRow();
		int colFrom = l.getCol();
		Location newLoc;
		switch(dir){
		case 1:
			newLoc = new Location(rowFrom - 1, colFrom);
			break;
		case 2:
			newLoc = new Location(rowFrom, colFrom + 1);
			break;
		case 3:
			newLoc = new Location(rowFrom + 1, colFrom);
			break;
		default:   // must be 4
			newLoc = new Location(rowFrom, colFrom - 1);
			break;
		}
		int rowTo = newLoc.getRow();
		int colTo = newLoc.getCol();
		s = rowFrom + " " + colFrom + " " + rowTo + " " + colTo;
		moves.push(s);
	}
	
	String strDir(int dir){
		String s;
		switch(dir){
		case UP:
			s = "up";
			break;
		case RIGHT:
			s = "right";
			break;
		case DOWN:
			s = "down";
			break;
		case LEFT:
			s = "left";
			break;
		default:
			s = "unspecified";
		}
		return s;
	}
	
	private void chkSolution(Board b){
		boolean tmpSoln = true;
		for (int i = 0; i < s.solLength() && tmpSoln; i++){
			Block blkDesired = s.getBlock(i);
			Location locDesired = s.getLocation(i);
			Block blkActual = b.layout[locDesired.getRow()][locDesired.getCol()];
			tmpSoln = blkDesired.equals(blkActual);
		}
		solved = tmpSoln;
	}
	
	/**
	 * Required configuration for the puzzle to be considered solved.
	 * Provides accessor functions for the number of blocks that need
	 * to be arranged in a specific location, as well as the associated 
	 * properties of those blocks.
	 * @author Jim
	 *
	 */
	private class Solution{
		ArrayList<Block> blks; 		//blocks that form solution
		ArrayList<Location> locs;	//expected locations
		int numOfBlks; 				//number of blocks required
		Solution(ArrayList<Block> b, ArrayList<Location> l){
			blks = b;
			locs = l;
			numOfBlks = blks.size();
		}
		/**
		 * Returns the Block object at the specified index.
		 * @param i - index location of Block to be returned
		 * @return A Block object.
		 */
		Block getBlock(int i){
			return blks.get(i);
		}
		/**
		 * Returns the a Location for the corresponding to the Block at 
		 * the specified index. 
		 * @param i - index of Location to be returned.
		 * @return A Location object.
		 */
		Location getLocation(int i){
			return locs.get(i);
		}
		/**
		 * Accessor function to get the number of blocks that need to be in a specific
		 * location to solve t puzzle.
		 * @return int - number of blocks
		 */
		int solLength(){
			return numOfBlks;
		}
	}
	
	private class Block{
		private int height,
					width;
		
		Block(int h, int w){
			height = h;
			width = w;
		}
		
		int getHeight(){
			return height;
		}
		
		int getWidth(){
			return width;
		}
		
		boolean equals(Block b){
			if (b == null)
				return false;
			return ((height == b.height) && (width == b.width));
		}
	}
	
	private class Location{
		private int row,
					col;
		
		Location(int r, int c){
			row = r;
			col = c;
		}
		
		int getRow(){
			return row;
		}
		
		int getCol(){
			return col;
		}
		
		boolean equals(Location l){
			return ((row == l.row) && (col == l.col));
		}
		
		public String toString(){
			return "(" + row + ", " + col + ")";
		}
	}
	
	private Board parseConfig(String fileName){
		int rows = 0;
		int cols = 0;
		ArrayList<Block> blks = new ArrayList<Block>();
		ArrayList<Location> locs = new ArrayList<Location>();
		FileReader file;
		BufferedReader fileIn = null;
		String oneLine;
		StringTokenizer str;
		
		try {
			file = new FileReader(fileName);
			fileIn = new BufferedReader(file);
			oneLine = fileIn.readLine();
			str = new StringTokenizer(oneLine);
			rows = Integer.parseInt(str.nextToken());
			cols = Integer.parseInt(str.nextToken());
			while ((oneLine = fileIn.readLine()) != null) {
				str = new StringTokenizer(oneLine);
				Block b = new Block(Integer.parseInt(str.nextToken()),
									Integer.parseInt(str.nextToken()));
				blks.add(b);
				Location l = new Location(Integer.parseInt(str.nextToken()),
										Integer.parseInt(str.nextToken()));
				locs.add(l);
			}
		} catch(IOException e){
			System.out.println(e);
		} finally {
			// Close the stream
			try {
				if (fileIn != null)
					fileIn.close();
			} catch(IOException e){
				
			}
		}
		return new Board(rows, cols, blks, locs);
	}
	
	private Solution parseSol(String fileName){
		ArrayList<Block> blks = new ArrayList<Block>();
		ArrayList<Location> locs = new ArrayList<Location>();
		FileReader file;
		BufferedReader fileIn = null;
		String oneLine;
		StringTokenizer str;
		
		try {
			file = new FileReader(fileName);
			fileIn = new BufferedReader(file);
			while ((oneLine = fileIn.readLine()) != null) {
				str = new StringTokenizer(oneLine);
				Block b = new Block(Integer.parseInt(str.nextToken()),
									Integer.parseInt(str.nextToken()));
				blks.add(b);
				Location l = new Location(Integer.parseInt(str.nextToken()),
										Integer.parseInt(str.nextToken()));
				locs.add(l);
			}
		} catch(IOException e){
			System.out.println(e);
		} finally {
			// Close the stream
			try {
				if (fileIn != null)
					fileIn.close();
			} catch(IOException e){
				
			}
		}
		return new Solution(blks, locs);
	}


	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int i = 0;
		Solver puzzle = new Solver();
		// TODO Auto-generated method stub
		if (args[0].substring(0, 2).equalsIgnoreCase("-o")){	// check 1st 2 char for debug option
			i++;
			if (args[0].substring(2).equalsIgnoreCase("debug"))
				debug = true;
			else if (args[0].substring(2).equalsIgnoreCase("option")){
				System.out.println("-odebug  =  print default debug information");
				return;
			}
		}
		// assuming well-formed arg list, with valid, accessible files
		Board b = puzzle.parseConfig(args[i++]);
		puzzle.s = puzzle.parseSol(args[i++]);
		puzzle.chkSolution(b);
		if (puzzle.solved){
			return;
		} else if(puzzle.tryMoving(b)){
			int k = puzzle.moves.size();
			for (int j = 0; j < k; j++){
				System.out.println(puzzle.moves.pop());
			}
		} else{
			System.exit(1);
		}
	}
	
	private static void debugPrint(String s){
		if (debug)
			System.out.println(s);
	}
	
}
